/*
 * @lc app=leetcode.cn id=238 lang=cpp
 *
 * [238] 除自身以外数组的乘积
 */
class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> fromBegin(n);
        fromBegin[0] = 1;
        vector<int> fromLast(n);
        fromLast[0] = 1;

        for (int i = 1; i < n; i++)
        {
            fromBegin[i] = fromBegin[i - 1] * nums[i - 1];
            fromLast[i] = fromLast[i - 1] * nums[n - i];
        }

        vector<int> res(n);
        for (int i = 0; i < n; i++)
        {
            res[i] = fromBegin[i] * fromLast[n - 1 - i];
        }
        return res;
    }
};
